package com.fr.lintcode;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

public class Q614ii {

	/**
	 * @param root: the root of binary tree
	 * @return: the length of the longest consecutive sequence path
	 */
	public int longestConsecutive2(TreeNode root) {
		// write your code here
		int max = 0;
		if (root == null) {
			return 0;
		}
		Map<TreeNode, Map<Integer, Integer>> map = new HashMap<>();
		longestConsecutive2(root, 0, map);
		longestConsecutive2(root, 1, map);
		for (Map.Entry<TreeNode, Map<Integer, Integer>> entry : map.entrySet()) {
			int i = entry.getValue().get(0) + entry.getValue().get(1);
			if (i > max) {
				max = i;
			}
		}
		return max - 1;
	}

	private int longestConsecutive2(TreeNode node, int i, Map<TreeNode, Map<Integer, Integer>> map) {
		if (node == null) {
			return 0;
		}
		if (i == 1) {
			int left = 0;
			int right = 0;
			if (node.left != null) {
				if (node.val - node.left.val == 1) {
					left = longestConsecutive2(node.left, i, map);
				} else {
					longestConsecutive2(node.left, i, map);
				}
			}
			if (node.right != null) {
				if (node.val - node.right.val == 1) {
					right = longestConsecutive2(node.right, i, map);
				} else {
					longestConsecutive2(node.right, i, map);
				}
			}
			int max = Math.max(left, right) + 1;
			Map<Integer, Integer> tmp = map.get(node);
			if (tmp == null) {
				tmp = new HashMap<>();
				map.put(node, tmp);
			}
			tmp.put(i, max);
			return max;
		} else if (i == 0) {
			int left = 0;
			int right = 0;
			if (node.left != null) {
				if (node.val - node.left.val == -1) {
					left = longestConsecutive2(node.left, i, map);
				} else {
					longestConsecutive2(node.left, i, map);
				}
			}
			if (node.right != null) {
				if (node.val - node.right.val == -1) {
					right = longestConsecutive2(node.right, i, map);
				} else {
					longestConsecutive2(node.right, i, map);
				}
			}
			int max = Math.max(left, right) + 1;
			Map<Integer, Integer> tmp = map.get(node);
			if (tmp == null) {
				tmp = new HashMap<>();
				map.put(node, tmp);
			}
			tmp.put(i, max);
			return max;
		}
		return 0;
	}

	@Test
	public void tesA() {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		n1.left = n2;
		n2.right = n3;
		n1.right = n5;
		n2.left = n4;
		System.out.println(longestConsecutive2(n1));
	}

}
